
#include <iostream>
#include <vector>

using namespace std;

/**
***************************************
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
***************************************
* Definition for singly-linked list.
*/
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
	ListNode * addTwoNumbers(ListNode *l1, ListNode *l2) {
		ListNode preHead(0), *p = &preHead; //pseudo header
		int extra = 0;
		while (l1 || l2 || extra) {
			int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + extra;
			extra = sum / 10;
			p->next = new ListNode(sum % 10);
			p = p->next;
			l1 = l1 ? l1->next : l1;
			l2 = l2 ? l2->next : l2;
		}
		return preHead.next;
	}

	ListNode* addTwoNumbers1(ListNode* l1, ListNode* l2)
	{
		ListNode *result;
		ListNode *dump = new ListNode((int)0);
		ListNode **sum = &result;
		int carry = 0;
		int now = 0;
		while (l1 != dump || l2 != dump || carry != 0)
		{
			now = (l1->val + l2->val + carry) % 10;
			carry = (l1->val + l2->val + carry) / 10;
			*sum = new ListNode(now);
			sum = &(*sum)->next;
			if (l2->next == NULL)
				l2 = dump;
			else l2 = l2->next;
			if (l1->next == NULL)
				l1 = dump;
			else l1 = l1->next;
		}
		delete dump;
		return result;
	}

	ListNode * addTwoNumbers0(ListNode* l1, ListNode* l2) {
		ListNode *pseudo_head = nullptr;
		ListNode *cur = nullptr;
		ListNode *node = nullptr;
		ListNode *tail = nullptr;
		int sum = 0;
		int shift = 0;

		pseudo_head = new ListNode(0);		
		cur = pseudo_head;
		while (l1 != nullptr && l2 != nullptr)
		{
			node = new ListNode(0);
			sum = l1->val + l2->val + shift;
			if (sum < 10)
			{
				node->val = sum;
				shift = 0;
			}
			else
			{
				node->val = (sum % 10);
				shift = 1;
			}
			cur->next = node;
			cur = node;

			l1 = l1->next;
			l2 = l2->next;
		}
		
		if (l1 != nullptr) tail = l1;
		if (l2 != nullptr) tail = l2;

		while (tail != nullptr)
		{
			node = new ListNode(0);
			sum = tail->val + shift;
			if (sum < 10)
			{
				node->val = sum;
				shift = 0;
			}
			else
			{
				node->val = sum % 10;
				shift = 1;
			}			
			node->next = nullptr;
			cur->next = node;
			cur = node;
			tail = tail->next;
		}

		if (shift != 0)
		{
			node = new ListNode(0);
			node->val = shift;
			shift = 0;
			cur->next = node;
			cur = node;
		}

		return pseudo_head->next;
	}

	ListNode * addTwoNumbersx(ListNode *l1, ListNode *l2) {
		int x = 0, y = 0, carry = 0, sum = 0;
		ListNode *h = NULL, **t = &h;

		while (l1 != NULL || l2 != NULL) {
			x = getValueAndMoveNext(l1);
			y = getValueAndMoveNext(l2);

			sum = carry + x + y;

			ListNode *node = new ListNode(sum % 10);
			*t = node;
			t = (&node->next);

			carry = sum / 10;
		}

		if (carry > 0) {
			ListNode *node = new ListNode(carry % 10);
			*t = node;
		}

		return h;
	}
	int getValueAndMoveNext(ListNode* &l) {
		int x = 0;
		if (l != NULL) {
			x = l->val;
			l = l->next;
		}
		return x;
	}	
};

void vec2list(vector<int> vec, ListNode ** list)
{
	ListNode *node = nullptr;
	ListNode *cur = nullptr;

	for (auto itr = vec.begin(); itr != vec.end(); ++itr)
	{		
		//node = (ListNode *)malloc(sizeof(ListNode));
		//node->val = *itr;
		//node->next = nullptr;

		node = new ListNode(*itr);
		if (itr == vec.begin())
		{
			*list = node;
			cur = node;
		}
		else
		{
			cur->next = node;
			cur = node;
		}
	}
}

void printvec(vector<int> vec)
{
	for (auto num : vec)
	{
		cout << num << " ";
	}
	cout << endl;
}

void printlist(ListNode * list)
{	
	while (list != nullptr)
	{
		cout << list->val << endl;
		list = list->next;
	}

	cout << endl;
}

int _addTwoNumbers()
{
	Solution solu;
	ListNode *l1 = nullptr;
	ListNode *l2 = nullptr;
	ListNode *cur = nullptr;
	ListNode *lr = nullptr;
	vector<int> nums1 = {1};// { 1, 8 };// {5};// { 2, 4, 3 };
	vector<int> nums2 = { 9,9 };// {0};// { 5 };// { 5, 6, 4 };

	vec2list(nums1, &l1);
	vec2list(nums2, &l2);

	cout << "list 1:" << endl;
	printlist(l1);
	
	cout << "list 2:" << endl;
	printlist(l2);
	
	lr = solu.addTwoNumbers(l1, l2);

	cout << "list result:" << endl;
	printlist(lr); 

	return 0;
}